package middle;

public class Solution_91 {

    public int numDecodings(String s) {
        int[] nums = new int[s.length()];
        char[] chars = s.toCharArray();
        for (int end = chars.length - 1; end >= 0; end--) {
            int c = chars[end] - '0';
            if (c > 0) {
                if (end == (chars.length - 1)) {
                    nums[end] = 1;
                } else {
                    nums[end] += nums[end + 1];
                    int next = chars[end + 1] - '0';
                    if (c == 1 || (c == 2 && next < 7)) {
                        // 只有当个位数是0～6 且 十位数是1或者2的时候，才是一个有效的数字
                        if (end + 2 >= chars.length) {
                            nums[end] += 1;
                        } else {
                            nums[end] += nums[end + 2];
                        }
                    }
                }
            }
        }
        return nums[0];
    }

    private int dps(char[] chars, int end) {
        if (end < 0) {
            return 1;
        }
        int c = chars[end] - '0';
        if (end == 0) {
            return c > 0 ? 1 : 0;
        } else {
            int num1 = 0, num2 = 0;
            if (c > 0) {
                num1 = dps(chars, end - 1);
            }
            int pre = chars[end - 1] - '0';
            if (pre == 1 || (pre == 2 && c < 7)) {
                // 只有当个位数是0～6 且 十位数是1或者2的时候，才是一个有效的数字
                num2 = dps(chars, end - 2);
            }
            return num1 + num2;
        }
    }

    public static void main(String[] args) {
        Solution_91 model = new Solution_91();
        System.out.println(model.numDecodings("111111111111111111111111111111111111111111111"));
        System.out.println(model.numDecodings("2611055971756562"));
        System.out.println(model.numDecodings("12"));
        System.out.println(model.numDecodings("226"));
        System.out.println(model.numDecodings("0"));
        System.out.println(model.numDecodings("9"));
    }
}
